package com.tucc.hello.leetcode.no1601_2000.no1751;

import cn.hutool.core.date.StopWatch;
import cn.hutool.core.io.FileUtil;

import java.util.Arrays;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
//        int[][] events = {{1,2,4},{3,4,3},{2,3,10}};
        int[][] events = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}};
        int k = 3;
        System.out.println(solution.maxValue(events, k));

        String path = "C:\\Users\\tucc38782\\Desktop\\test.txt";
        String text = FileUtil.readUtf8String(path).trim();
        text = text.substring(2, text.length() - 2);
        String[] parts = text.split("\\],\\[");
        events = new int[parts.length][];
        for (int i = 0; i < events.length; i++) {
            String[] partNums = parts[i].split(",");
            events[i] = new int[partNums.length];
            for (int j = 0; j < partNums.length; j++) {
                events[i][j] = Integer.parseInt(partNums[j]);
            }
        }
        k = 1;
        StopWatch stopWatch = new StopWatch();
        stopWatch.start();
        System.out.println(solution.maxValue(events, k));
        stopWatch.stop();
        System.out.println(stopWatch.getTotalTimeMillis());
    }

    private int MAX = 0;

    public int maxValue(int[][] events, int k) {
        if(k == 0){
            return 0;
        }
//        if(k == 1){
//            int max = events[0][2];
//            for(int i = 1;i < events.length;i ++){
//                if(events[i][2] > max){
//                    max = events[i][2];
//                }
//            }
//            return max;
//        }
        Arrays.sort(events, (a, b) -> {
            int r = a[0] - b[0];
            return r == 0 ? a[1] - b[1] : r;
        });
        maxValueDp(events, k);
        return MAX;
    }

    public int maxValueDp(int[][] events, int k) {
        if (k == 0) {
            return 0;
        }
        int[][] dp = new int[events.length][k + 1];
        for (int i = 0; i < events.length; i++) {
            dp[i][1] = events[i][2];
            if (events[i][2] > MAX) {
                MAX = events[i][2];
            }
        }
        for (int i = 1; i <= events.length; i++) {
            int[] curEvent = events[i - 1];
            for (int j = 2; j <= k && j <= i; j++) {
                int max = 0;
                for (int m = i - 2; m >= 0; m--) {
                    if (dp[m][j - 1] > max && events[m][1] < curEvent[0]) {
                        max = dp[m][j - 1];
                    }
                }
                dp[i - 1][j] = max + curEvent[2];
                if (dp[i - 1][j] > MAX) {
                    MAX = dp[i - 1][j];
                }
            }
        }
        return MAX;
    }

    public int maxValueRecursion(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> {
            int r = a[0] - b[0];
            return r == 0 ? a[1] - b[1] : r;
        });
        for (int i = 0; i < events.length; i++) {
            maxValue(events, k, i + 1, 1, events[i][2],
                    events[i][1]);
        }
        return MAX;
    }

    public void maxValue(int[][] event, int k, int curIndex,
                         int curJoin, int curSum, int max) {
        if (curJoin == k || curIndex == event.length) {
            if (curSum > MAX) {
                MAX = curSum;
            }
            return;
        }
        while (curIndex < event.length && event[curIndex][0] <= max) {
            curIndex++;
        }
        if (curIndex == event.length) {
            if (curSum > MAX) {
                MAX = curSum;
            }
            return;
        }
        int[] curEvent = event[curIndex];
        // 参加当前
        maxValue(event, k, curIndex + 1, curJoin + 1, curSum + curEvent[2],
                curEvent[1]);
        //不参加当前
        maxValue(event, k, curIndex + 1, curJoin, curSum, max);
    }

}
